#include <iostream>
#include "euler.h"

BEGIN_PROBLEM(323, solve_problem_323)
	PROBLEM_TITLE("Bitwise-OR operations on random integers")
	PROBLEM_ANSWER("6.3551758451")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("n^2")
	PROBLEM_SPACE_COMPLEXITY("n")
	PROBLEM_KEYWORDS("probability")
END_PROBLEM()

static void solve_problem_323()
{
	const int count = 32;
	double N[count+1];
	int C[count+1] = {1};

	N[0] = 0;
	unsigned int denom = 1;
	for (int k = 1; k <= count; k++)
	{
		// Compute C(k,i).
		C[k] = 1;
		for (int i = k-1; i >= 1; i--)
			C[i] += C[i-1];

		// Compute N(k).
		double t = 1.0;
		for (int i = 1; i < k; i++)
		{
			t += C[i] * N[i];
		}
		N[k] = 1.0 + t / denom;
		denom = (denom << 1) | 1;
		//std::cout.precision(10);
		//std::cout << "N(" << k << ") = " << std::fixed << N[k] << std::endl;
	}
	std::cout.precision(10);
	std::cout << std::fixed << N[count] << std::endl;
}
